# 考察BFS/DFS
from collections import deque


def solution(N: int, M: int, data: list[list[str]]) -> int:
    # 预定义方向和传送器类型
    DIRECTIONS = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    TRANSPORTERS = set(DIRECTIONS.keys())

    visited = [[False for _ in range(M)] for _ in range(N)]
    queue = deque()

    # 初始化：找到所有出口
    for i in range(N):
        for j in range(M):
            if data[i][j] == 'O':
                queue.append((i, j))
                visited[i][j] = True

    reachable_count = 0

    while queue:
        x, y = queue.popleft()
        reachable_count += 1

        # 检查四个方向
        for dx, dy in DIRECTIONS.values():
            nx, ny = x + dx, y + dy

            # 边界检查
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # 处理传送器逻辑
                if data[nx][ny] in TRANSPORTERS:
                    tdx, tdy = DIRECTIONS[data[nx][ny]]
                    if nx + tdx == x and ny + tdy == y:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                else:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    return N * M - reachable_count


if __name__ == '__main__':
    print(solution(N=5, M=5, data=[
        [".", ".", ".", ".", "."],
        [".", "R", "R", "D", "."],
        [".", "U", ".", "D", "R"],
        [".", "U", "L", "L", "."],
        [".", ".", ".", ".", "O"]
    ]) == 10)
    print(solution(N=4, M=4, data=[
        [".", "R", ".", "O"],
        ["U", ".", "L", "."],
        [".", "D", ".", "."],
        [".", ".", "R", "D"]
    ]) == 2)
    print(solution(N=3, M=3, data=[
        [".", "U", "O"],
        ["L", ".", "R"],
        ["D", ".", "."]
    ]) == 8)
